package main

import (
	"container/heap"
	"container/list"
	"container/ring"
	"fmt"
)

type IntHeap []int

func (h IntHeap) Top() int            { return h[0] }
func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{}   { n := len(*h); r := (*h)[n-1]; *h = (*h)[0 : n-1]; return r }

type Item struct {
	index  int
	value  string
	weight int
}

type PriorityQueue []*Item

func (q PriorityQueue) Top() *Item          { return q[0] }
func (q PriorityQueue) Len() int            { return len(q) }
func (q PriorityQueue) Less(i, j int) bool  { return q[i].weight > q[j].weight }
func (q PriorityQueue) Swap(i, j int)       { q[i], q[j] = q[j], q[i]; q[i].index, q[j].index = i, j }
func (q *PriorityQueue) Push(x interface{}) { x.(*Item).index = len(*q); *q = append(*q, x.(*Item)) }
func (q *PriorityQueue) Pop() interface{}   { n := len(*q); r := (*q)[n-1]; *q = (*q)[0 : n-1]; return r }
func (q *PriorityQueue) Modify(item *Item)  { heap.Fix(q, item.index) }

func main() {
	// Heap
	h := &IntHeap{1, 2, 3, 5, 6}
	heap.Init(h)
	heap.Push(h, 2)
	fmt.Println("min:", h.Top())

	for h.Len() > 0 {
		fmt.Println(heap.Pop(h))
	}

	// Priority Queue
	q := &PriorityQueue{
		{0, "lychee", 3},
		{0, "orange", 4},
		{0, "banana", 5},
	}
	heap.Init(q)
	fmt.Printf("max:%+v\n", q.Top())
	q.Top().weight = 1
	q.Modify(q.Top())

	for q.Len() > 0 {
		fmt.Printf("%+v\n", heap.Pop(q))
	}

	// List
	l := list.New()
	e1 := l.PushFront(1)
	e4 := l.PushBack(4)
	l.InsertBefore(3, e4)
	l.InsertAfter(2, e1)

	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()

	// Ring
	r := ring.New(9)
	for i := 1; i <= r.Len(); i++ {
		r.Value = i
		r = r.Next()
	}

	r.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()

	r = r.Next()
	r.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()

	r = r.Prev()
	r.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()

	r1 := r.Unlink(3)
	r.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()
	r1.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()

	r.Link(r1)
	r.Do(func(v interface{}) {
		fmt.Printf("%v ", v)
	})
	fmt.Println()

}
